// 归并
function mergeSort(arry){
    // 1.分配辅助数组
    const len = arry.length
    const  tmp = new Array(len)
    // 2.拆分
    const  sort = (arr,left,right)=>{
        if(left < right){
            // 1.找中间点
            let middle = Math.floor(( left + right) / 2)
            // 2.继续划分左右区域
            sort(arr,left,middle)
            sort(arr,middle + 1,right)
            // 3.合并排序
            merge(arr,left,middle,right)
        }
    }
    // 3.合并
    const merge = (arr,left,middle,right)=>{
        // 1.标记左右半区未排序元素、临时数组下标
        let [l_pos,r_pos] = [left,middle+1]
        let pos = left // 需要合并 left~right 这一段
        // 2.合并（合并后可能有剩余，所以有了 3,4）
        while(l_pos <= middle && r_pos <= right){
            if(arr[l_pos] < arr[r_pos]){
                tmp[pos++] = arr[l_pos++]
            }else{
                tmp[pos++] = arr[r_pos++]
            }
        }
        // 3.合并左半区剩余元素
        while(l_pos <= middle){
            tmp[pos++] = arr[l_pos++]
        }
        // 4.合并右半区剩余元素
        while(r_pos <= right){
            tmp[pos++] = arr[r_pos++]
        }
        // 5.把修改原始数组
        while(left <= right){
            arr[left] = tmp[left]
            left ++
        }
    }
    sort(arry,0,len-1)
}


// 快排
function quickSort(arry){
    const len = arry.length
    const sort = (arr,low,high)=>{
       if(low < high){
            const middle = partition(arr,low,high)
            // 左半区
            sort(arr,low,middle-1)
            // 右半区
            sort(arr,middle+1,high)
       }
    }
    const partition = (arr,i,j)=>{
        let low = i - 1,high = j
        const pivot = arr[high]
        while(1){
            while(arr[++low] < pivot); // low 右移
            while(arr[--high] > pivot); // high 左移
            if(low < high){
                [arr[low], arr[high]] = [arr[high], arr[low]]
            }else{
                break
            }
        }
        [arr[low], arr[j]] = [arr[j], arr[low]]
        return low
    }
    sort(arry,0,len-1)
}

// 堆排序
function heapSort(array,length=array.length){
    // 维护堆的性质
    const heapify = (arr,i,len = arr.length)=>{
        // 假设当前是最大的
        let maxIndex = i 
        // 左右节点
        let lchildIndex = i * 2 + 1
        let rchildIndex = i * 2 + 2
        // 找出当前节点左右孩子中最大的
        if(rchildIndex < len && arr[maxIndex] < arr[rchildIndex]){
            maxIndex = rchildIndex
        }
        if(lchildIndex < len && arr[maxIndex] < arr[lchildIndex] ){
            maxIndex = lchildIndex
        }
        // 需要调整
        if(maxIndex !== i){
            [arr[maxIndex],arr[i]] = [arr[i],arr[maxIndex]]
            heapify(arr,maxIndex,len)
        }
    }
    const sort = (arr,len=arr.length)=>{
        for (let i = len - 1; i > 0; i--) {
            [arr[i],arr[0]] = [arr[0],arr[i]]
            // 维护剩余元素性质
            heapify(arr,0,i) 
        }
    }
    let i = parseInt((length - 1 - 1)/2)
    for(;i>=0;i--){
        heapify(array,i)
    }
    sort(array)
}

// 希尔排序

function shellSort(array,len = array.length){
    // 初始增量为 array.length / 2，之后每趟除以 2
    for (let inc = parseInt(len / 2); inc > 0; inc = parseInt(inc/2)) {
        // 每趟采用插入排序
        for (let i = inc; i < len; i++) {
            let key = array[i]
            let j
            // key 比前一个 array[j-inc] 小才进行插入
            for (j = i; j >= inc && key < array[j-inc];j-=inc) {
                array[j] = array[j-inc]
            }
            // 把 key 放在正确的位置
            array[j] = key
        }
    }
}

// 计数
function countSort(array,min,max){
    const res = new Array(array.length)
    const count = new Array(max-min+1).fill(0)
    for (let i = 0; i < array.length; i++) {
        count[array[i]-min] ++        
    }
    // 累加数组，此时数组中的值是出现的最后一个下标
    // 比如：count = [3,4,5] 表示 0 出现 3 次，1 出现 4 次，2 出现 5 次；
    // 累加数组：[3,7,12] 表示 0 出现的最后一个下标是 3-1，1 出现的最后一个下标是 7-1，2 出现的最后一个下标是 12-1
    for (let i = 1; i < count.length; i++) {
        count[i] = count[i] + count[i-1]
    }
    // 从后往前迭代，把 array[i] 放在 res 中 count 值 -1 的位置
    for (let i = array.length-1; i >= 0; i--) {
        res[--count[array[i] - min]] = array[i]
    }
    return res
}

// 基数排序
function radixSort(array,k){
    const result = new Array(array.length)
    const count = new Array(10).fill(0)
    for (let i = 0; i < k; i++) {
        let division = Math.pow(10,i)
        // 以下为计数排序
        for (let j = 0; j < array.length; j++) {
            const num =  parseInt(array[j] / division) % 10
            count[num] ++            
        }
        for (let j = 1; j < count.length; j++) {
            count[j] = count[j] + count[j-1]  
        }
        for (let j = array.length - 1; j >= 0; j--) {
            let num  = parseInt(array[j] / division) % 10
            result [--count[num]]  = array[j]
        }
        array = JSON.parse(JSON.stringify(result))
        count.fill(0)
    }
    return array
}
const  arrs = [18,19,20,21,22,23,18,20,22,22,23,20,19,19]
// mergeSort(arrs)
// quickSort(arrs)
// heapSort(arrs)
// shellSort(arrs)
// const res = radixSort(arrs,2)

console.log(radixSort(arrs,2))

